package 动态规划.打家劫舍;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/20 18:38
 */
public class 打家劫舍II {

// 这个题 写的 有些 繁琐， 我们 通过 控制 传入参数的不同的，来使 方法体 相同！
   public int dp(int[] nums){
       int len = nums.length;
       if(len == 1){
           return nums[0];
       }
       int[] dp = new int [len + 1];
       dp[len - 1] = nums[len - 1];
       int temp = 0;
       for(int i = len - 2;i >= 1;i--){
           dp[i] = Math.max(dp[i + 1],dp[i + 2] + nums[i]);
       }
       temp = dp[1];
       dp[len - 2] = nums[len - 2];
       dp[len - 1] = 0;
       for(int i = len - 3; i >= 0;i--){
           dp[i] = Math.max(dp[i + 1], dp[i + 2] + nums[i]);
       }
       return Math.max(dp[0],temp);
   }

    // 就像下面这样， 思想 就是这样，但是 写的 好像有些繁琐！

    private class Solution {
        /**
         Everything is the same as the linear problem. Only difference is, when calculating the last two home's profit, consider about the initial two homes

         when interviewing, think about the linear issue first, then upgrade to this circle
         When analysing this circle, we can cut it to two linear problem:
         1. we start with the 1st home, then we cut the last one home from the circle; e.g.  1->2->3->4 can be converted to 1->2->3
         2. we start with the 2nd home, then we cut the first one home from the circle; e.g. 1->2->3->4 can be convert to 2->3->4
         **/
        public int rob(int[] nums) {
            if (nums == null || nums.length < 1) {
                return 0;
            } else if (nums.length < 4) {
                // if there is less than 4 homes, as there is a circle, we can at most steal one home
                int maxValue = 0;
                for (int i=0;i<nums.length; i++) maxValue = Math.max(maxValue, nums[i]);
                return maxValue;
            }
            // we have at least 4 homes here
            return Math.max(rob(nums,0,nums.length-2), rob(nums,1,nums.length-1));
        }

        private int rob(int[] nums, int start, int end) {
            // value is a cache containing
            // "max profit till last second home", "max profit till last home", "max profit till this home"
            int[] value = new int[3];
            for (int i = 0; i < 2; i++) {
                value[i] = nums[start+i];
            }

            // the third home will have its profit maxed by robbing the first home along
            value[2] = nums[start+2] + value[0];

            for (int i = 3; start+i <= end; i++) {
                // rob either like "x, o, o, x", or "o, x, o, x", see which one profit better
                int v = Math.max(value[0], value[1]) + nums[start+i];
                value[0] = value[1];
                value[1] = value[2];
                value[2] = v;
            }
            return value.length > 1 ? Math.max(value[value.length - 1], value[value.length - 2]) : value[0];
        }
    }

}
